package com.tgy.leetcode;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Author: tgy
 * @Date: 2/3/21 9:26 AM
 *
 *  https://leetcode-cn.com/problems/sliding-window-median/
 */
public class _480_滑动窗口中位数 {

    public static double[] medianSlidingWindow(int[] nums, int k) {

        double[] res = new double[nums.length - k + 1];

        double[] tmpNums =  new double[k];

        for (int i = 0; i < k; ++i) {
            tmpNums[i] = nums[i];
        }

        Arrays.sort(tmpNums);

        int midLeft,midRight = 0;
        boolean isEven = (k & 1) == 0;

        midLeft = (k -1) >> 1;
        if (isEven) {

            midRight = midLeft + 1;
        }

        for (int i = k; i <= nums.length; ++i) {
          //

            if (isEven) {

                res[i - k] = (tmpNums[midRight] - tmpNums[midLeft]) / 2.0 + tmpNums[midLeft];
            }else {

                res[i - k] = tmpNums[midLeft];
            }

            if (i == nums.length) {

                break;
            }

            int index = findIndex(tmpNums,nums[i-k],0,tmpNums.length);

            for(int j = index + 1; j < k;j++) {

                tmpNums[j - 1] = tmpNums[j];
            }

            // log(k)
            index = findFirstLargeIndexfindIndex(tmpNums,nums[i],0,tmpNums.length - 1);

            for (int j = k - 1;j > index;j--){
                tmpNums[j] = tmpNums[j - 1];
            }

            tmpNums[index] = nums[i];
        }


        return res;
    }

    public static int findIndex(double[] nums,int val, int start, int end) {


        int mid;

        while (start < end) {

            mid = ((end - start) >> 1) + start;

            if (nums[mid] > val) {

                end = mid;
            }else if (nums[mid] < val) {

                start = mid + 1;
            }else {

                return mid;
            }

        }

        return -1;
    }

    public static int findFirstLargeIndexfindIndex(double[] nums,int val, int start, int end) {

        int mid;

        while (start < end) {

            mid = ((end - start) >> 1) + start;

            if (nums[mid] > val) {

                end = mid;
            }else if(nums[mid] <= val){

                start = mid + 1;
            }
        }

        return start;
    }

    public static void main(String[] args) {


        PriorityQueue<Integer> queue = new PriorityQueue<>();



        int[] nums = {-2147483648,-2147483648,2147483647,-2147483648,-2147483648,-2147483648,2147483647,2147483647,2147483647,2147483647,-2147483648,2147483647,-2147483648};

        double[] res = medianSlidingWindow(nums, 3);

        System.out.println(Arrays.toString(res));

        System.out.println(Integer.MIN_VALUE);
    }
}
